package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/15 16:42
 * @description: TODO
 */
public class _049_并查集合 {

    @Test
    public void test1() {
        DisJointSet disJointSet = new DisJointSet(5);
        disJointSet.set(0, 0);
        disJointSet.set(1, 1);
        disJointSet.set(2, 2);
        disJointSet.set(3, 3);
        disJointSet.set(4, 4);

        disJointSet.union(0, 1);
        disJointSet.union(1, 2);
        disJointSet.union(2, 3);
        disJointSet.union(3, 4);
        System.out.println(disJointSet);
    }

    public static class DisJointSet {
        int[] s;
        int[] rank;

        private DisJointSet() {

        }

        public DisJointSet(int n) {
            s = new int[n];
            rank = new int[n];
            Arrays.fill(rank, 1); // 初始化rank为1
        }

        public int find(int x) { // 递归求出x的根节点
            if (s[x] == x) {
                return x;
            }
            return s[x] = find(s[x]); // 优化：路径压缩
        }

        public void union(int x, int y) {
            x = find(x);
            y = find(y);
            // 优化,让少的去连多的
            if (rank[x] > rank[y]) {
                rank[x] += rank[y];
                s[y] = x;
            } else {
                rank[y] += rank[x];
                s[x] = y;
            }
        }

        public void set(int x, int y) {
            s[x] = y;
        }

        @Override
        public String toString() {
            return Arrays.toString(s);
        }
    }
}
